package 剑指Offer.中等;

import Entity.TreeNode;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 请实现一个函数按照之字形顺序打印二叉树，
 * 即第一行按照从左到右的顺序打印，
 * 第二层按照从右到左的顺序打印，
 * 第三行再按照从左到右的顺序打印，
 * 其他行以此类推。
 * <p>
 *  
 * <p>
 * 例如:
 * 给定二叉树: [3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回其层次遍历结果：
 * <p>
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/9/21 9:43
 */
public class _32III从上到下打印二叉树III {

    public static void main(String[] args) {
        TreeNode a = new TreeNode(1);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(3);
        TreeNode d = new TreeNode(4);
        TreeNode e = new TreeNode(5);
        a.left = b;
        a.right = c;

        b.left = d;
        c.right = e;

        _32III从上到下打印二叉树III aa = new _32III从上到下打印二叉树III();
        List<List<Integer>> lists = aa.levelOrder(a);
        System.out.println();
    }


    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resList = new LinkedList<>();
        if (root == null) {
            return resList;
        }
        Queue<List<TreeNode>> queue = new LinkedList<>();
        List<TreeNode> treeNodeList = new LinkedList<>();
        treeNodeList.add(root);
        queue.add(treeNodeList);
        int deep = 0;

        while (!queue.isEmpty()) {

            List<TreeNode> poll = queue.poll();
            List<TreeNode> nextDeepList = new LinkedList<>();
            List<Integer> res = new LinkedList<>();

            // 首先将下一层的节点全收集起来
            for (TreeNode treeNode : poll) {
                if (treeNode.left != null) {
                    nextDeepList.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    nextDeepList.add(treeNode.right);
                }
            }
            // 然后再根据不同的深度进行不同顺序的遍历
            if (deep % 2 == 0) {
                // 从左到右
                for (TreeNode treeNode : poll) {
                    if (treeNode != null) {
                        res.add(treeNode.val);
                    }
                }
            } else {
                // 从右到左
                for (int i = poll.size() - 1; i >= 0; i--) {
                    TreeNode treeNode = poll.get(i);
                    if (treeNode != null) {
                        res.add(treeNode.val);
                    }
                }
            }
            resList.add(res);
            if (!nextDeepList.isEmpty()) {
                queue.add(nextDeepList);
            }
            deep++;
        }

        return resList;
    }
}
